#include <bits/stdc++.h>
using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

struct Com
{
    bool operator()(ListNode *a, ListNode *b)
    {
        return a->val > b->val;
    }
};

class Solution
{
public:
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        priority_queue<ListNode *, vector<ListNode *>, Com> q;
        for (auto e : lists)
        {
            if (e)
            {
                q.push(e);
            }
        }
        ListNode *dummyHead = new ListNode(-1);
        ListNode *cur = dummyHead;
        while (q.size() != 0)
        {
            ListNode *newNode = q.top();
            cur->next = newNode;
            cur = newNode;
            q.pop();
            if (newNode->next)
            {
                q.push(newNode->next);
            }
        }
        return dummyHead->next;
    }
};